perm filename A19.TEX[154,PHY] blob sn#815717 filedate 1986-04-23 generic text, type C, neo UTF8
COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\magnification\magstephalf
C00013 ENDMK
C⊗;
\magnification\magstephalf
\input macro.tex
\def\today{\ifcase\month\or
  January\or February\or March\or April\or May\or June\or
  July\or August\or September\or October\or November\or December\fi
  \space\number\day, \number\year}
\baselineskip 14pt
\rm
\line{\sevenrm a19.tex[154,phy] \today\hfill}

\parskip5pt
\parindent0pt
\bigskip
\noindent{\bf Congruence modulo $m$.}

\bigskip
The quotient $q=a$ {\tt DIV} $b$ and remainder $r=a$ {\tt MOD} $b$ on
division of integer $a$ by positive integer~$b$, are defined by
$$a=bq+r\,,\qquad 0≤r<b\,.$$
These values are unique; if also $a=bq'+r'$, by subtraction
$b(q-q')=r'-r$.
If $q≠q'$, $|b(q-q')|≥b$, while $|r'-r|<b$, impossible; so $q=q'$,
and $r=r'$.

We can say, for fixed $b$, that $a↓1$ is equivalent to $a↓2$ if they give
the same remainder on division by~$b$; this is the common method of
defining an equivalence by $a↓1=a↓2$ iff $f(a↓1)=f(a↓2)$. Since
the values of the function  are in $(0,b-1)$, there are only $b$
equivalence classes. In symbols $a↓1≡a↓2\pmod{b}$ means $a↓1\hbox{\tt \ MOD }b
=a↓2\hbox{\tt \ MOD }b$.

\medskip
\disleft 38pt::
{\bf Drill:} Show $a↓1≡a↓2\pmod{b}$ iff $a↓1-a↓2$ is a multiple of~$b$.

\medskip
\disleft 38pt::
{\bf Proof.} $a↓1=q↓1b+r↓1$, $a↓2=q↓2b+r↓2$. If $r↓1=r↓2$, $a↓1-a↓2=
b(q↓1-q↓2)$. If $a↓1-a↓2=nb$ and $a↓1=q↓1b+r↓1$, $a↓2=(q↓1-n)b+r↓1$,
and $a↓1≡a↓2(\bmod b)$.

\medskip\noindent
If $x↓1≡x↓2$, $y↓1≡y↓2\pmod{b}$, then $x↓1+y↓1≡x↓2+y↓2$, $x↓1-y↓1≡x↓2-y↓2$,
and $x↓1y↓1≡x↓2y↓2$.

\medskip\noindent
Proof of $x↓1y↓1≡x↓2y↓2$:
$x↓1y↓1-x↓2y↓2=(x↓1y↓1-x↓1y↓2)+(x↓1y↓2-x↓2y↓2)
=x↓1(y↓1-y↓2)+(x↓1-x↓2)y↓2$.
Since $y↓1-y↓2$ and $x↓1-x↓2$ are multiples of $b$, the whole thing is.

\medskip
\disleft 38pt::
{\bf Drill:} Prove the other two assertions.

\medskip
Let $p$ be a prime. If $ab≡0\pmod{p}$, then either $a≡0$ or $b≡0\pmod{p}$.

\medskip\noindent
{\bf Proof.} Suppose $ab≡0$ for some $a$ and $b$, neither $≡0$. Then
there is a smallest such (positive)~$a$; assume that's the one we are
looking at. Divide $p$ by~$a$, giving
$$p=aq+r\,,\qquad 0≤r<a\,.$$
Then $rb≡(p-aq)b≡pb-(ab)q≡0$; since $r$ is smaller than~$a$, it must be~0,
and $p=aq$. 

A prime is defined as having no divisors except itself and~1, so $a=p$
or $a=1$. If $a=p$, $a≡0\pmod{p}$, absurd. If $a=1$, $0≡ab=1\cdot b=b$,
absurd. The above proof is implicitly by course-of-values induction.


\bigskip
\parindent0pt
\copyright 1984 Robert W. Floyd

First draft September 10, 1984

\vfill\eject

\noindent{\bf Theorem.} Any FML in which all strings are of prime length
is finite. 

\smallskip\noindent
{\bf Proof:} If infinite, it contains a pumpable string $uvw$, of prime
length~$p$. Then $uv↑{p+1}w$ has length $p(1+{\rm length}\ v)$, which is
not prime. So the set of primes written in unary notation $(1↑p)$ is not
a~FML, and does not even contain an infinite FML.

\smallskip\noindent
{\bf Theorem.} Any FML consisting entirely of prime numbers (written
as decimal numerals without leading zeroes) is finite. Thus the set of
primes, in decimal, does not even contain an infinite subset which is
an FML.

\smallskip\noindent
{\bf Proof:} If infinite, it contains a pumpable string $uvw$, where
$uv↑0w↓{(10)}=uw↓{(10)}>5$, and where each $x↓i=uv↑iw↓{(10)}$ is prime.
Letting $b=$~length$(v)>0$, $c=$~length$(w)$,
$$\eqalign{x↓i&=(uv↑i)↓{(10)}\cdot 10↑c+w↓{(10)}\cr
x↓{i+1}&=(uv↑i)↓{(10)}\cdot 10↑{b+c}+v↓{(10)}\cdot 10↑c+w↓{(10)}\,.\cr}$$
Eliminating $(uv↑i)↓{(10)}\cdot 10↑c$ between them,
$$\eqalign{x↓{i+1}&=10↑bx↓i+\bigl(v↓{(10)}\cdot 10↑c-w↓{(10)}(10↑b-1)\bigr)\cr
&=d\,x↓i+e\,,\cr}$$
where $d≥10$ is divisible by no prime greater than~5. The problem is now
to show that no such sequence can consist entirely of primes.

Let $x↓0$ be the prime $p=uw↓{(10)}>5$, and define $y↓i=x↓i\hbox{\tt{ MOD }}p$.
If $1≤i<j$, and $y↓i=y↓j$, then
$$\eqalign{&(d\,x↓{i-1}+e)\hbox{ {\tt MOD }}p=(d\,x↓{j-1}+e)\hbox{ {\tt MOD }}p\,;\cr
&(d\,x↓{i-1})\hbox{ {\tt MOD }}p=(d\,x↓{j-1})\hbox{ {\tt MOD }}p\,;\cr
&d(x↓{i-1}-x↓{j-1})\hbox{ {\tt MOD }}p=0\,;\cr}$$
since $p$ does not divide $d$, it divides $x↓{i-1}-x↓{j-1}$, so if 
$y↓i=y↓j$, then $y↓{i-1}=y↓{j-1}$. In the sequence $y↓0,y↓1,y↓2,\ldots$,
there must be a first repetition $y↓i=y↓j$. If $i$ were not zero there would
be an earlier repetition $y↓{i-1}=y↓{j-1}$, so $0=p\bmod p=y↓0=y↓j=x↓j\bmod p$,
$x↓j$~is divisible by~$p$, and $x↓j$ is not prime. By {\sl reductio
ad absurdum\/}, the FML is finite.

\medskip
\disleft 38pt::
{\bf Drill:} Where was the assumption used that the primes are written
without leading zeroes? Is the theorem true without that qualification?

\smallskip\noindent
{\bf Theorem.} Any CFL consisting entirely of prime numbers (written as
decimal numbers without leading zeroes) is finite. 

\smallskip\noindent
{\bf Proof:} Analogous to that for FML's, using the CFL pumping lemma,
but replacing the relation $x↓{i+1}=d\,x↓i+e$ with $x↓{i+1}=d\,x↓i+e\,x↓{i-1}+f$.

\smallskip\noindent
{\bf Definition.} A language $L$ is 1-pumpable if almost all strings in it
have the form $uvw$, where $uv↑{\ast}w\subseteq L$. It is 2-pumpable if
almost all strings in it have the form $uvwxy$, where $uv↑iwx↑iy\subseteq L$.

\smallskip\noindent
{\bf Sketch of proof:} prime numbers not a CFL.
$$\eqalign{z↓i&=\;uv↑i\;w\,x↑i\,y↓{10}\cr
z↓{i+1}&=\;uv↑i\;v\,w\,x↑i\,x\,y↓{10}\cr}$$
$$\eqalign{z↓{i+1}-z↓i\cdot 10↑{\left| vx\right|}
&=\underline{vwx↑i}xy↓{(10)}-10↑{\left|vx\right|}\cdot 
\underline{wx↑i}y↓{(10)}\cr
z↓{i+2}-z↓{i+1}\cdot 10↑{\left| vx\right|}
&=\underline{vwx↑i}xxy↓{(10)}-10↑{\left|vx\right|}\cdot 
\underline{wx↑i}xy↓{(10)}\,.\cr}$$
Eliminate underlined portion:
$$(z↓{i+2}-z↓{i+1}\cdot 10↑{\left|vx\right|})-(z↓{i+1}-z↓i\cdot
10↑{\left|vx\right|})\cdot 10↑{\left|x\right|}=
(xxy↓{(10)}-10↑{\left|vx\right|}\cdot xy↓{(10)})-10↑{\left|x\right|}
(xy↓{(10)}-10↑{\left|vx\right|}\cdot y↓{(10)})\,,$$
so $z↓{i+2}=d\,z↓{i+1}+e\,z↓i+f$.

\smallskip\noindent
{\bf Theorem.} Any FML in which the lengths of all strings are perfect
squares is finite.

\smallskip\noindent
{\bf Proof:} If infinite, it contains a pumpable string $uvw$. Let
$a={\rm length}(uw)$, $b={\rm length}(v)≥1$. The pumped string
$uv↑{ba↑2}w$ has length $b\cdot ba↑2+a$, which lies between the
consecutive perfect squares
$(ba)↑2$ and $(ba+1)↑2=b↑2a↑2+2ab+1$\bblackslug

\smallskip\noindent
{\bf Theorem.} The set of perfect squares written as decimal numbers is
not an FML.

\smallskip\noindent
{\bf Proof:} If it is, take a perfect square $(10↑n20↑n1)↓{(10)}$ where
$n$~comes from the pumping lemma. Pumping twice among the first $n$~zeroes,
we get $(10↑{n+2a}20↑n1)↓{(10)}$ which lies between the two
consecutive perfect squares
$(10↑{2(n+a+2)})↓{(10)}$ and $(10↑{n+a}20↑{n+a}1)↓{(10)}$.


\bigskip
\parindent0pt
\copyright 1984 Robert W. Floyd

First draft July 18, 1984

\bye